import java.util.ArrayDeque;

public class L226 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(4);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(7);
        treeNode.left = left;
        treeNode.right = right;

        new Solution().invertTree(treeNode);
    }

    static class Solution {

        public TreeNode invertTree(TreeNode root) {
            ArrayDeque<TreeNode> deque = new ArrayDeque<>();
            deque.offer(root);
            while (!deque.isEmpty()) {
                int size = deque.size();
                while (size > 0) {
                    size--;
                    TreeNode node = deque.poll();
                    swap(node);
                    if (node.left != null) {
                        deque.offer(node.left);
                    }
                    if (node.right != null) {
                        deque.offer(node.right);
                    }
                }
            }
            return root;
        }

//        public TreeNode invertTree(TreeNode root) {
//            if (root == null) {
//                return null;
//            }
//            invertTree(root.left);
//            invertTree(root.right);
//            swap(root);
//            return root;
//
//        }

        private void swap(TreeNode root) {
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
        }
    }
}
